package list;

/**
 * 双向循环链表类
 */
public class LinkedList<E> {

    //head用于存放头节点的引用
    private Node head;

    //size用于存放链表的长度
    private int size = 0;

    /**
     * Node类用于描述链表中的某个节点，
     * 其中，data用于存放数据（即元素），
     * next和prev用于存放其后继节点和前驱节点的引用。
     */
    class Node{
        E data;
        Node next;
        Node prev;
        public Node(E e) {
            data = e;
        }
    }

    /**
     * 将元素添加到链表的末尾。
     * @param e 要添加的元素。
     * @return 添加成功，返回true。100
     */
    public boolean add(E e){
        //将元素封装成节点
        Node node = new Node(e);
        //如果链表为空，则新节点成为头节点
        if(head == null){
            head = node;//80
            head.next = head;
            head.prev = head;
            //链表的长度加1
            size ++;
            return true;
        }
        //找到尾节点
        Node last = head.prev;//90
        //将新节点添加到尾节点后面
        last.next = node;//90的下一个新来的100
        node.next = head;//100的下一个也指向80
        head.prev = node;//80的上一个指向100
        node.prev = last;//100上一个是90
        size ++;
        return true;
    }

    @Override
    public String toString() {
        if(head == null){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        sb.append(head.data);
        Node node = head.next;
        while(node != head){
            sb.append("," + node.data);
            node = node.next;
        }
        return sb.append("]").toString();
    }

    /**
     * 返回链表的长度
     */
    public int size(){
        return size;
    }

    /**
     * 返回指定位置（下标）处的元素
     * @param index 下标
     * @return 该位置对应的节点里面存放的数据（即元素）
     */
    public E get(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("下标越界");
        }
        Node node = getNode(index);
        //返回该节点中存放的数据
        return node.data;
    }

    /*
        依据下标找到某个节点。
        （了解）：这是一个帮助器(helper方法),即只在当前类中使用，
        并且为其它方法服务的方法。
     */
    private Node getNode(int index) {
        //从头节点开始找指定位置的节点
        Node node = head;
        //为了提高运行的速度，这儿可以通过比较index与链表长度的一半来决定
        //是顺时针（查找后继节点）还时逆时针（查找前驱节点）查找。
        if(index < size >> 1){
            for(int i = 0; i < index; i ++){
                node = node.next;
            }
        }else{
            for(int i = size; i > index; i --){
                node = node.prev;
            }
        }
        return node;
    }

    /**
     * 删除指定位置的元素
     */
    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("下标越界");
        }
        //如果链表中只有一个节点，则需要将head设置为null。
        if(size == 1){
            E data = head.data;
            head = null;
            size --;
            return data;
        }
        //找到要删除的节点
        Node node = getNode(index);
        //找到该节点的上一个节点（前驱）和下一个节点（后继）
        Node prev = node.prev;
        Node next = node.next;
        //在prev和next之间建立引用关系
        prev.next = next;
        next.prev = prev;
        //如果要删除的是头节点，则其下一个节点成为头节点。
        if(index == 0){
            head = next;
        }
        //链表长度减1
        size --;
        //返回被删除的元素
        return node.data;
    }

    /**
     * 根据索引修改数据
     * @param index
     * @param ele
     * @return
     */
    public E set(int index,E ele){
        if (index < 0 || index >= size){        //索引小于0或者大于等于数据总个数,就会下标越界
            throw new IndexOutOfBoundsException("下标越界");
        }
        Node node = getNode(index); //获取索引对应的数据地址
        E data = node.data;         //把数据给泛型
        remove(index);              //删除索引对应的数据
        data=ele;
        add(ele);                  //添加一个新数据
        return ele;
    }
}